
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 2025. -- [SHOI2009] 交通网络 -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>2025: [SHOI2009] 交通网络</h2><span class=green>Time Limit: </span>10 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>66&nbsp;&nbsp;<span class=green>Solved: </span>14<br>[<a href='submitpage.php?id=2025'>Submit</a>][<a href='problemstatus.php?id=2025'>Status</a>][<a href='bbs.php?id=2025'>Discuss</a>]</center><h2>Description</h2><div class=content><p>著名的城市交通规划师L.Serenade为OItown的各个城堡之间设计了一套的地铁交通网络。每一条地铁线路都用来双向连通两个城堡。因为是建在地下的不同深度，所以这些地铁线路是可以&ldquo;交叉&rdquo;的。 OItown的居民们的生活和工作都在不同的城堡中进行，于是，每个OItown的居民都要在每天早晨从家出发，乘地铁去工作，当然地铁换乘是允许的。不过每个居民都会选择换乘次数最少的乘车方式。如果有多种乘车方式，这些乘车方式所需要的换乘次数一样，那么居民每天都会等概率的随机选择其中一种。现在L.Serenade想请你为他计算出，每天每条地铁线路在早晨的平均客流量。他会告诉你，每个居民的家和工作地址，还有他设计的地铁交通网络的全部信息。当然L.Serenade保证，交通网络能把城市连为一体，而且任意两个城堡之间的最优乘车方式（即换成次数最少的）不超过263-1种。</p></div><h2>Input</h2><div class=content><p>输入文件的第一行有两个整数n、m，分别表示OItown里的城堡数（这些城堡用1.2.3...n标号）和地铁线路的数量。接下去m行，每行包含两个整数，x、y，表示这两个城堡之间有一条地铁线路。注意，两个城堡之间最多只有一条地铁线路，且每条地铁线路只被输入文件描述一次。最后的n行，每行有n个整数。第i行的第j个非负整数Ci，j表示每天早晨有Ci，j个OItown的居民要从i城堡去j城堡。输入数据保证Ci，i=0。</p></div><h2>Output</h2><div class=content><p>输出文件有m行，每行依次表示每条地铁线路每天早晨的平均客流。精确到小数点后一位。整数也应输出一位小数，例如1应输出为1.0。</p></div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>6 7<br />
1 2<br />
1 3<br />
2 4<br />
2 5<br />
3 5<br />
4 6<br />
5 6<br />
0 0 0 0 0 1<br />
0 0 0 0 0 0<br />
0 0 0 0 0 0<br />
0 0 0 0 0 0<br />
0 0 0 0 0 0<br />
0 0 0 0 0 0<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>0.7<br />
0.3<br />
0.3<br />
0.3<br />
0.3<br />
0.3<br />
0.3<br />
0.7</span></div><h2>HINT</h2>
			<div class=content><p><p>样例说明：从城堡1到城堡六的使得换乘次数最少的乘车方式共有3种：1-2-4-6；1-2-5-6；1-3-5-6。所以每个人都有1/3的概率选择这其中的每一种。 N&lt; = 300 M&lt; = N*(N-1) div 2 0&lt; = C(i,j) &lt; = 100</p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Day1'>Day1</a></p></div><center>[<a href='submitpage.php?id=2025'>Submit</a>][<a href='problemstatus.php?id=2025'>Status</a>][<a href='bbs.php?id=2025'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
